#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include "ArrayList.h"

struct stArrayList_t* ArrayList_New(int (*comp)(void*, void*)) {
	struct stArrayList_t *list = (struct stArrayList_t*)malloc(sizeof(struct stArrayList_t));
	list->size = 0;
	list->capacity = DEFAULT_CAPACITY;
	list->collection = (void**)malloc(sizeof(void*)*list->capacity);
	list->comp = comp;
	return list;
}

struct stArrayList_t* ArrayList_NewWithSize(int (*comp)(void*, void*), int capacity) {
	struct stArrayList_t *list = (struct stArrayList_t*)malloc(sizeof(struct stArrayList_t));
	list->size = 0;
	list->capacity = capacity;
	list->collection =(void**) malloc(sizeof(void*)*list->capacity);
	list->comp = comp;
	return list;
}

void ShiftUp(struct stArrayList_t* list, int index) {
	int i;
	for(i = list->size; i > index; i--) {
		list->collection[i] = list->collection[i - 1];
	}
}

void IncreaseSize(struct stArrayList_t* list) {
	void** new = malloc(sizeof(void*)*list->capacity*SIZE_INCREMENTATION_FACTOR);
	int i;

	for(i = 0; i < list->size; i++) {
		new[i] = list->collection[i];
	}
	free(list->collection);
	list->collection = new;
	list->capacity = list->capacity*SIZE_INCREMENTATION_FACTOR;
}

void ArrayList_Insert(struct stArrayList_t* list, int index, void* element) {
	if(index > list->size || index < 0) {
		return; /* Invalid */
	}
	if(list->size == list->capacity) {
		IncreaseSize(list);
	}
	ShiftUp(list, index);
	list->collection[index] = element;
	list->size++;
}

void ArrayList_Add(struct stArrayList_t* list, void* element) {
	if(list->size == list->capacity) {
		IncreaseSize(list);
	}
	list->collection[list->size++] = element;
}

void ArrayList_Clear(struct stArrayList_t* list) {
	free(list->collection);
	list->collection = (void**)malloc(sizeof(void*)*DEFAULT_CAPACITY);
	list->size = 0;
	list->capacity = DEFAULT_CAPACITY;
}

int ArrayList_Contains(struct stArrayList_t* list, void* element) {
	return ArrayList_IndexOf(list, element) != -1;
}

void* ArrayList_Get(struct stArrayList_t* list, int index) {
	if(index < 0 || index > list->size - 1) {
		return NULL; /* Invalid index */
	}
	return list->collection[index];
}

int ArrayList_IndexOf(struct stArrayList_t* list, void* element) {
	int i;
	for(i = 0; i < list->size; i++) {
		if((*list->comp)(list->collection[i], element) == 0) {
			return i;
		}
	}
	return -1;
}

int ArrayList_IsEmpty(struct stArrayList_t* list) {
	return list->size == 0;
}

void* ArrayList_RemoveAt(struct stArrayList_t* list, int index) {
	int i;
	void* temp;

	if(index > list->size || index < 0) {
		return NULL; /* Invalid index */
	}
	temp = ArrayList_Get(list, index);
	for(i = index; i < list->size - 1; i++) {
		list->collection[i] = list->collection[i + 1];
	}
	list->size--;
	return temp;
}

void* ArrayList_Remove(struct stArrayList_t* list, void* element) {
	int i;
	int index = -1;
	void* temp;

	for(i = 0; i < list->size; i++) {
		if((*list->comp)(list->collection[i], element) == 0) {
			index = i;
		}
	}
	temp = ArrayList_RemoveAt(list, index);
	return temp;
}

int ArrayList_GetSize(struct stArrayList_t* list) {
	return list->size;
}

void ArrayList_Set(struct stArrayList_t* list, int index, void* element) {
	if(index > list->size - 1 || index < 0) {
		return; /* Invalid index */
	}
	list->collection[index] = element;
}

void ArrayList_BubbleSort(struct stArrayList_t* list) {
	void **start, **end, **itr;
	void *temp;
	char sorted;

	if(list->size == 0) {
		return;
	}
	start = list->collection;
	end = list->collection + list->size;
	do {
		sorted = 1;
		for(itr = start; (itr+1) != end; itr++) {
			if((*list->comp)(*itr, *(itr+1)) > 0) {
				temp = *itr;
				*itr = *(itr+1);
				*(itr+1) = temp;
				sorted = 0;
			}
		}
		end--;
	} while(!sorted);
}

#define LeftChildOf(x) ((2 * x) + 1)
#define ParentOf(x) ((x - 1) / 2)

void ArrayList_HeapSort(struct stArrayList_t* list) {
	int parent_index, child_index, right_child, left_child, max_child, heap_size = 1;
	void* temp;

	/* construct heap */
	while(heap_size < list->size) {							/* while the heap does not include the entire collection */
		child_index = heap_size++;							/* add new element to heap */
		parent_index = ParentOf(child_index);				/* find parent of newly added element */
		while(parent_index > -1 && (*list->comp)(list->collection[child_index],
			list->collection[parent_index]) > 0) {			/* while the child element is larger than parent element */
			temp = list->collection[child_index];			/* swap child and parent elements */
			list->collection[child_index] = list->collection[parent_index];
			list->collection[parent_index] = temp;
			child_index = parent_index;						/* set child index to parent index */
			parent_index = ParentOf(child_index);			/* find parent of new child index */
		}
	}

	/* shrink heap */
	while(heap_size > 1) {									/* while the heap is larger than 1 */
		parent_index = --heap_size;							/* find last element in heap */
		temp = list->collection[0];							/* swap last element with first element */
		list->collection[0] = list->collection[parent_index];
		list->collection[parent_index] = temp;
		parent_index = 0;									/* set parent to first element in heap */
		while(1) {											/* while true */
			left_child = LeftChildOf(parent_index);			/* find the largest child for our parent */
			if(left_child >= heap_size) {					/* if no child exists, stop */
				break;
			}
			right_child = left_child + 1;
			max_child = left_child;
			if(right_child < heap_size &&
				(*list->comp)(list->collection[right_child],
				list->collection[left_child]) > 0) {
				max_child = right_child;
			}
			if((*list->comp)(list->collection[max_child],
				list->collection[parent_index]) > 0) {		/* if the largest child is larger than the parent */
				temp = list->collection[max_child];			/* swap largest child with parent */
				list->collection[max_child] = list->collection[parent_index];
				list->collection[parent_index] = temp;
				parent_index = max_child;					/* set parent index to that of the max child */
			} else {										/* if the parent is greater than or equal to the child, stop */
				break;
			}
		}
	}
}

void** ArrayList_CopyData(struct stArrayList_t* list) {
	void** out = malloc(sizeof(void*) * list->size);
	void** start = list->collection;
	void** end = list->collection + list->size;

	while(start != end) {
		*out++ = *start++;
	}
	out -= list->size;
	return out;
}

void ArrayList_Finalize(struct stArrayList_t* list) {
	free(list->collection);
	free(list);
}

int ArrayList_StringComparison(char* one, char* two) {
	return strcmp(one, two);
}

int ArrayList_AddressComparison(void* one, void* two) {
	if(one > two) {
		return 1;
	} else if(two > one) {
		return -1;
	} else {
		return 0;
	}
}

int ArrayList_IntegerComparison(int* one, int* two) {
	if(*one > *two) {
		return 1;
	} else if(*two > *one) {
		return -1;
	} else {
		return 0;
	}
}
